Any object of interest in the world can be represented by corresponding information, or data. Information or data can then be processed so that people may have access to it. As known to people skilled in the art and as used in the specification throughout, among other things, the term data generally refers to numerical, graphical or alphabetical information representing one or more objects of interest. Data may be obtained or reduced through empirical observations or from instrument readings. The term data processing generally refers to various operations on data. In particular, among other functions, data processing includes data recording, transmission of data, manipulation of data, data conversion, data reporting, data reconstruction, storage of data, retrieval of data, and usage of data.
One aspect of data processing relates to digital data processing. Modern digital data processing of functions (or signals or images) always uses a discretized version of the original signal ƒ that is obtained by sampling ƒ on a discrete set. The question then arises whether and how ƒ can be recovered from its samples, which often is termed as “sampling problem”. Therefore, among other things, one objective of research on the sampling problem is to quantify the conditions under which it is possible to recover particular classes of functions from different sets of discrete samples, and a related objective is to use these analytical results to develop explicit reconstruction schemes for the analysis and processing of digital data. Specifically, the sampling problem often includes two main parts as follows:                (a) First, given a class of functions V on d, find conditions on sampling sets X={xjεd:jεJ}, where J is a countable index set, under which a function ƒεV can be reconstructed uniquely and stably from its samples {ƒ(xj):xjεX)}; and        (b) Second, find efficient and fast numerical algorithms that recover any function ƒεV from its samples on X.        
In some applications, it may be justified to assume that the sampling set X={xj:jεJ} is uniform, i.e., that X forms a regular n-dimensional Cartesian grid, where n is an integer greater than zero. For examples, as shown in FIG. 1, curve 101 representing a function ƒ is sampled on a one-dimensional uniform grid 103. Moreover, as shown in FIG. 2, grid 203 represents a two-dimensional Cartesian grid. These grids can find some uses in real world and can be used to practice the present invention. For example, a digital image is often acquired by sampling light intensities on a uniform grid. Data acquisition requirements and the ability to process and reconstruct the data simply and efficiently often justify this type of uniform data collection.
However, in many realistic situations the data are known only on a nonuniformly spaced sampling set. This nonuniformity is a fact of life and prevents the use of the standard methods from Fourier analysis. Correspondingly, several nonuniform grids, such as a polar sampling grid 213, a spiral sampling grid 223, and a nonuniform grid 233, all schematically shown in FIG. 2, can find some more uses in real world and can be used to practice the present invention. The following examples are typical and indicate that nonuniform sampling problems are more pervasive in science and engineering.
Communication theory and practice: When data from a uniformly sampled signal (function) are lost, the result is generally a sequence of nonuniform samples. This scenario is usually referred to as a missing data problem. Often, missing samples are due to the partial destruction of storage devices, e.g., scratches on a CD. As shown in FIG. 3, a missing data problem is simulated by randomly removing samples from a slice of a three-dimensional magnetic resonance (MR) digital image 301. The simulated image 303 with 50% random missing samples displays a rather incomplete construction of image 301 and loses important details of image 301. Image 303 can be considered as a sampling of image 301, which is the object of interest at this example, on the nonuniform grid 233.
Astronomical measurements: The measurement of star luminosity gives rise to extremely nonuniformly sampled time series. Daylight periods and adverse nighttime weather conditions prevent regular data collection as further discussed in [111].
Medical imaging: Computerized tomography (CT) and magnetic resonance imaging (MRI) frequently use the nonuniform polar sampling grid 213 and spiral sampling grid 223 as further discussed in [21, 90], respectively.
Other applications using nonuniform sampling sets occur in geophysics as further discussed in [92], spectroscopy as further discussed in [101], general signal/image processing as further discussed in [13, 22, 103, 106], and biomedical imaging such as MRI as discussed above in connection with images 301 and 303 and ultrasonic images 401 and 403 as shown in FIG. 4 and as further discussed in [20, 59, 90, 101], respectively. For examples, as shown in FIG. 4, detected edge points 402 of the left ventricle of a heart from a two-dimensional ultrasound image 401 constitute a nonuniform sampling of the left ventricle's contour, while boundary 404 of the left ventricle shown is reconstructed from the detected edge sample points 402. More information about modern techniques for nonuniform sampling and applications can be found in [16].
Efforts have been made accordingly to find better, fast and efficient techniques for nonuniform data sampling and data reconstruction such that one can reconstruct an object of interest from nonuniform data sampling with limit data points, and/or can convert from digital type (i.e., some data points) to analog type (i.e., a corresponding image), or vice versa.
However, among other things, standard methods of signal processing and data sampling encounter several problems as follows:
First, these methods often are not local due to the infinite range of the band limited function model utilized by these methods.
Second, these methods are not multi-dimensional, i.e., they do not work well for signals related to time series, images, 3-D images, spectral images as well as samples of any high dimensional images with dimension larger than 3.
Third, these methods are normally not that fast. In fact, standard methods based on Fast Fourier Transformation (“FFT”) are currently fastest methods one can get. Still, in an ideal situation, it has an order of a computational complexity NlogN that is slow when N is large, where N is the order of the samples.
Fourth, these methods may not be easily utilized in association with parallel processing because the non-localization due to the infinite range of the band limited function model utilized by these methods, which further limits the ability of these methods to take advantages of computing power offered by parallel processing.
Therefore, there is a need to develop system and methods for nonuniform sampling and applications of data representing an object to address the aforementioned deficiencies and inadequacies.